1. Field of the Invention
The present invention relates to a method for compressing digital data to compressed data, which comprises a stream of data words and control words. The present invention further relates to a method of decompressing compressed data to digital data and to a computer program product, an application specific programming unit, a controller computer and a print engine, configured to perform said method
2. Background of the Invention
A known print system comprises a print engine that marks a receiving material with toner or ink to form a printed image. The input data may come from a scanner or another source of digital images. Access to the print engine is controlled by a networked general purpose computer that uses an application, called a controller program, that accepts print jobs through the network, interprets the print jobs and transforms them to image data, which are sent to the print engine and saved in the computer memory for later reference. A computer with this application may be called a controller computer. The image data comprises the information for the print engine to make a complete printed page. In the print engine, a number of print pixels is defined, which are regularly distributed and associated with a position on the receiving material. For each print pixel, the image data comprises information whether or not to mark the receiving material with toner or ink. In a bitonal print engine the amount of toner or ink for each print pixel is fixed and therefore this information is represented by one bit. In contrast, in a multilevel print engine, various amounts of toner or ink may be associated with a print pixel and more than one bit is necessary to represent this information in the image data.
One of the transformations that is performed on the print jobs is known as (digital) halftoning, which is part of the Raster Image Processing. In this process, the content of the bits that determine the distribution of toner or ink over the page is established. One familiar type of halftoning is dithering, that employs a matrix of thresholds to which the pixel values that come from a rasterizing process are compared. The threshold values in the matrix define a screen that is apparent in the printed image. The matrix, in general being smaller than the image, is shifted in two directions to obtain a threshold value for each pixel. The image data after halftoning are bitonal data, when every bit signifies one of two tone levels in the image for every print pixel.
The image data that are generated in the controller program are transferred to the print engine. Over the years, the number of print pixels in the print engines has steadily increased and accordingly the amount of image data has increased. However, depending on the speed of the print engine, i.e. the number of printed pages per minute, there is only limited time for data transfer. An A4 page comprising 1200 dpi in both directions, having two tone levels per print position, has a bitonal data size of about 140 Mbit. Therefore the transfer speed of the data bus between the controller computer and the print engine for black/white images of a 60 pages per minute print system has to exceed 140 Mbit/s. In a CMYK color printer this speed is four times as high, as each process color is associated with a bitonal image of this data size. To reduce the necessary transfer speed, it is beneficial to consider compressing the bitonal data.
A number of constraints restrict the use of known compression schemes. First of all there may be only limited processing power, because the CPU of the controller computer is involved in more tasks than compressing. Secondly, the decompression scheme is preferably simple, referencing only a part of the processed data, because only these are still kept in memory, which has only a finite size. Further, the compression factor, which is the ratio between the amount of compressed data relative to the amount of original data, for pages with little information, may be around 0.01, but for pages comprising a complex full-page picture, the compression factor should not exceed 0.5. A low compression factor indicates that the compressed data is much smaller than the original data, whereas a high compression factor indicates that the compressed data is hardly smaller than the original data. A final constraint is that the compression is preferably lossless to make sure that there is no visible difference between the printing of the original image data and the printing of the compressed data after decompression. Familiar lossless run-length encoding schemes, like ITU-T Group4 compression, are not capable of combining these constraints. Run-length encoding schemes typically use data words that correspond to the original data and control words that include a run-length code to indicate the number of times a data word is repeated or copied. This may be combined with backward referencing to already processed data words. This requires specific control codes that are taken up in the control words. It is advantageous for the compression if a word occurs repeatedly in the stream of data words, because the control code is usually shorter than the original data word. In hardware-implemented methods, words may have a length of 1 bit, or 8 bits (1 byte), but in software-implemented methods words often have a length of 2, 4, or even 8 bytes, corresponding to a preferred word length of the CPU.
An object of the present invention is to find a lossless compression scheme that combines the specific demands for the communication between a controller computer and a print engine.